1. Field of Invention
The present invention relates generally to network systems. More particularly, the present invention relates to enabling a backup label switched path (LSP) to be created to bypass a border router, and to enable substantially unambiguously determined if the backup LSP that bypasses a border router merges with a primary LSP that passes through the border router.
2. Description of the Related Art
The demand for data communication services is growing at an explosive rate. Much of the increased demand is due to the fact that more residential and business computer users are becoming connected to the Internet. Furthermore, the types of traffic being carried by the Internet are shifting from lower bandwidth applications towards high bandwidth applications which include voice traffic and video traffic.
As the Internet becomes a multi-media communications medium that is expected to reliably handle voice and video traffic, network protocols must also evolve to support quality-of-service (QoS) requirements such as latency and reliability and to provide guaranteed available bandwidths. One form that this evolution is taking is the advent of MPLS (Multi-Protocol Label Switching) Traffic Engineering which may be supplemented by Diffserv-aware Traffic Engineering. Rather than using conventional IP routing techniques where individual packets travel through the network following paths determined individually for each packet as it progresses through the network, MPLS Traffic Engineering exploits modern label switching techniques to build guaranteed bandwidth end-to-end circuits through a network of label switched routers (LSRs). MPLS has been found to be highly useful in establishing such circuits also referred to as label switched paths (LSPs). MPLS networks employing LSPs may more easily interoperate with other IP-based networks than other virtual circuit-oriented networks employing, e.g., ATM or Frame Relay. Networks based on MPLS Traffic Engineering, especially those supplemented with DiffServ-aware Traffic Engineering are very effective in handling delay and jitter-sensitive applications such as voice over IP (VoIP) and real-time video.
Meeting the demands of businesses and consumers, however, also requires that bandwidth and latency guarantees continue to be met when links or nodes fail. When failure of a link or a node causes the failure of an LSP, the standard routing protocols such as open shortest path first (OSPF) are too slow to be used for fast rerouting of loss-sensitive traffic. In optical networks employing SONET, fast restoration may be provided by means of features incorporated into the SONET protocol. However, where such techniques are not available, other protection mechanisms become necessary to ensure that services are restored within a sufficiently short time, e.g., 50 ms, such that the user experience is not affected.
A network is generally designed to ensure that information may be transferred between nodes within the network. Often, within a network, information is transferred between two specified nodes, i.e., a source node which sends information and a destination node which receives information. When information is to be sent between a source node and a destination node, a circuit path between the two nodes must be established so that leased line services may be provided. Typically, in MPLS networks, LSPs form circuit paths between the two nodes.
An LSP that has been established to carry traffic between a pair of nodes during normal operation, i.e., in the absence of a network node or link failure, is called a primary LSP. Nodes and links that are a part of a primary LSP may suffer failures during the course of operation. In order to ensure that the traffic which is being sent on the primary path may still reach an appropriate destination in the event of a failure within the primary LSP, the links and nodes on the primary LSP may be bypassed. MPLS fast reroute (FRR) is a local protection recovery technique that is often used to bypass nodes and/or links within a network. Nodes and links may be bypassed by one or more LSPs, and such LSPs are called backup LSPs. The path of a backup LSP generally must not include a link or a node that it bypasses.
In order to provide the desired response time upon failure detection, FRR solutions have concentrated on defining backup LSPs in advance so that an appropriate backup LSP may be activated upon detection of a failure very quickly, e.g., typically within a few milliseconds. Traffic may then be rerouted by the node immediately upstream of the failure. As will be appreciated by those skilled in the art, with an FRR technique, a primary LSP may be protected from the failure of a particular node or link on the path of that primary LSP. In an FRR context, a backup LSP may or may not provide end-to-end protection to a corresponding primary LSP. Path protection, on the other hand, is a mechanism which enables a backup LSP to provide end-to-end protection to a corresponding primary LSP.
With FRR, when a protected node or link failure occurs, traffic carried by primary LSPs passing through the protected node or link is switched to the appropriate backup LSP or LSPs that have previously been set up. FIG. 1 is a diagrammatic representation of nodes which are interconnected with a primary LSP and various backup LSPs. Nodes 110 are connected through links 112 within an overall network 100. For example, node 110a and node 110b are connected by link 112a, and node 110b is connected to node 110c by link 112b. The path of a primary LSP 114 is defined to includes nodes 110 and links 112 such that primary LSP 114, as shown, substantially begins at node 110a and ends at node 110e. 
Backup LSPs 116 are arranged to bypass various nodes 110 and links 112 when node 110 or link 112 failures occur. A first backup LSP 116a is a next hop (NNHOP) backup LSP that bypasses node 110b and allows traffic to be re-routed substantially around node 110b in the event that node 110b fails. A second backup LSP 116b is an NNHOP backup LSP that bypasses node 110d, while a third backup LSP 116c is an NNHOP backup LSP that bypasses node 110c. A fourth backup LSP 116d is a next hop (NHOP) backup LSP that bypasses link 112c in the event that link 112c fails. It should be appreciated that although other links 112 may also have associated backup LSPs if such links 112 are protected links, such backup LSPs have not been shown for ease of illustration.
As shown, backup LSPs 116 do not pass through the elements that they bypass. By way of example, since backup LSP 116d bypasses link 112c, backup LSP 116d does not pass through link 112c. Likewise, since backup LSP 116a bypasses node 110b, backup LSP 116a does not pass through node 110b. 
A primary LSP and a backup LSP should intersect at least at two nodes. A head-end of the backup LSP intersects the primary LSP at a Point of Local Repair (PLR), while a tail-end of the backup LSP intersects the primary LSP at a Merge Point. As will be appreciated by those skilled in the art, the PLR is where the FRR may be triggered when a node or a link failure occurs. When an LSP requesting FRR protection is first set up, a PLR generally needs to select a backup LSP to be used in case of a link or node failure that intersects the primary LSP on a downstream node. In order to select an appropriate backup LSP, the PLR is required to gather information on the set of downstream nodes traversed by the LSP. The gathering of such information typically involves making use of a record route object (RRO) carried in a resource reservation protocol (RSVP) reservation message. If a Merge Point does not exist between a primary LSP and a backup LSP, the PLR does not send traffic from the primary LSP over the backup LSP if the relevant node or link fails.
With reference to FIG. 2, the location of a PLR and a merge point with respect to a primary LSP and a backup LSP will be described. Nodes 210 and links 212 are included in a primary LSP 214. A backup LSP 216 is arranged to bypass node 210b. Backup LSP 216 intersects primary LSP 214 at a PLR 210a and a merge point 210c. Typically, PLR 210a and merge point 210c are nodes that are substantially adjacent to node 210b, which is being bypassed by backup LSP 216. In other words, backup LSP 216 that bypasses node 210b is a NNHOP backup LSP. Hence, when node 210b fails, traffic that is being routed through primary LSP 214 is re-routed through backup LSP 216 between PLR 210a and merge point 210c, thereby effectively protecting primary LSP 214 from the failure of node 210b. 
When nodes 210 are located within a single Interior Gateway Protocol (IGP) area, e.g., OSPF, or a single IGP level, e.g., intermediate system to intermediate system (ISIS), PLR 210a may determine if primary LSP 214 and backup LSP 216 intersect at merge point 210c by examining the RRO of primary LSP 214 along with the tail-end address of backup LSP 216. Since nodes 210 are located within a single area or level, for example, all nodes 210 are aware of the full connectivity of all nodes 210, i.e., the IGP topology of all nodes, within the single IGP area or level. The RRO of primary LSP 214 is specified in terms of node-identifiers (node-IDs) of nodes 210 in addition to, or in lieu of, the interface identifiers to nodes 210. Hence, within a single area, or level, or autonomous system, PLR 210a has knowledge of substantially all interfaces attached to the tail-end of backup LSP 216, namely merge point 210c. As a result, by using its IGP topology, PLR 210a may unambiguously identify merge point 210c regardless of whether the RRO of primary LSP 214 specifies node-IDs or interface identifiers.
Backup LSPs may generally be computed using a variety of different methods. A user or a network administrator may statically configure backup LSPs at PLRs. For example, a user of a network administrator may to establish a backup LSP with a path that he or she explicitly specifics. A PLR may also be configured to substantially automatically compute a backup LSP that is diversely routed from the node or the link which is being bypassed by the backup LSP. More specifically, there may be a dynamic process that allows a backup LSP to be dynamically found and established. When configured appropriately, a PLR computes a suitable path and triggers the establishment of the backup LSP. In general, there may be some timer that may be configured to remove backup LSPs that are not being used. This is possible, for instance, if all primary LSPs which were protected by a particular backup LSP are torn down.
A PLR generally may not arbitrarily assign a backup LSP that bypasses a given node or link to protect a given primary LSP that passes through the node or link being bypassed by the backup LSP. In order to be able to protect a primary LSP from the failure of a bypassed node or link, a backup LSP should intersect with the primary LSP at both the PLR and the merge point, as discussed above. Each backup LSP may also be configured to substantially guarantee an acceptable bandwidth during a node or link failure. That is, a backup LSP effectively satisfies the bandwidth requirements associated with the primary LSP which is protected by the backup LSP.
Currently, a PLR may not unambiguously determined if a merge point exists between a backup LSP and a primary LSP when a node that is to be bypassed is a border node, e.g., a boundary or border router, which is located substantially at the border of either an IGP area or level, or an autonomous system. FIG. 3a is a diagrammatic representation of a primary LSP which includes border routers and spans two IGP areas of an autonomous system. An autonomous system 306 includes areas 308. A primary LSP 314 includes nodes 310 and links 312. Node 310b is an area border router.
In order to attempt to bypass node 310b, a backup LSP (not shown) would span both area 308a and area 308b. For example, in order to bypass node 310b, a backup LSP may be established between nodes 310a and 310c. With such a backup LSP, node 310a is a PLR. To assign the backup LSP to primary LSP 314, node 310a, as the PLR, should be able to determine if node 310c is on the path of primary LSP 314. That is, a PLR should determine if a merge point exists between a backup LSP and primary LSP 314 in order to assign the backup LSP to primary LSP 314. Since a PLR may not use its IGP topology to determine the interfaces connected to node 310c, i.e., the tail-end of the backup LSP, it is generally not possible to assign the backup LSP to primary LSP 314. In other words, since a PLR in one area 308a has no access to the topology of a tail-end of a proposed backup LSP that is in another area 308b, the PLR may not unambiguously assign a backup LSP that bypasses border node 310b to primary LSP 314 that spans multiple IGP areas. Hence, a PLR may not determine a merge point without ambiguity.
Similarly, it may not be possible to unambiguously find a backup LSP for protecting a primary LSP from the failure of an asynchronous system border node when the primary LSP spans multiple autonomous systems. As will be appreciated by those skilled in the art, such an LSP is called an inter-autonomous system LSP (inter-AS LSP). FIG. 3b is a diagrammatic representation of a primary LSP which effectively spans two autonomous systems. Nodes 360 and links 362 are on the path of a primary LSP 374 which is partially in a first autonomous system 356 and a second autonomous system 358. Node 360b is a border router as node 360b is located at the borders of autonomous system 356 and autonomous system 358. A PLR, as for example node 360a when node 360b is to be bypassed, may not know the topology of a tail-end of a proposed backup LSP (not shown) whose tail-end is in autonomous system 358. That is, a PLR does not have knowledge of interfaces which are connected to the tail-end of a proposed backup LSP that is partially in autonomous system 356 and partially in autonomous system 358. As such, since a merge point is a point at which the tail-end of a proposed backup LSP intersects primary LSP 374, the location of such a merge point may not be unambiguously identified by the PLR in order to assign a backup LSP to primary LSP 374.
The ability to protect primary LSPs passing through area border routers or autonomous system border routers from the failure of such router via an FRR mechanism reduces the traffic loss to failure in MPLS networks with inter-area or inter-AS traffic engineering. Minimizing such traffic loss is important for providing better services to users. When backup LSPs which protect border routers may not be substantially automatically determined, the ability of service providers to protect inter-area or inter-AS primary traffic engineering from the failure of border routers is generally compromised.
Therefore, what is needed is a method and an apparatus which allows NNHOP backup LSPs which protect border routers to be substantially automatically determined by a PLR. More specifically, what is desired is a system which enables merge points associated with primary LSPs and backup LSPs which protect either area border routers or autonomous system border routers to be substantially unambiguously identified.